from math import sqrt
from tools_algorithm import *

# Q1. 优质数对的总数 I


class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        ans = 0
        for i, vi in enumerate(nums1):
            for j, vj in enumerate(nums2):
                if vi % (vj * k) == 0:
                    ans += 1

        return ans


# Q2. 压缩字符串 III
class Solution:
    def compressedString(self, word: str) -> str:
        ans = []
        cnt = 0
        for i, v in enumerate(word):
            if i == 0 or (v == word[i - 1] and cnt < 9):
                cnt += 1
            else:
                ans.append(str(cnt) + word[i - 1])
                cnt = 1
        if cnt > 0:
            ans.append(str(cnt) + word[-1])

        return "".join(ans)


a = 10**6
b = 1
cnt = 0
while b < a:
    cnt += 1
    b <<= 1
print(b, cnt)
print(pow(2, 20))
print(sqrt(a))
class PrimeFactor:

    def __init__(self, ceil):
        self.ceil = ceil  # 上限
        self.prime_factor = [[] for _ in range(self.ceil + 1)]  # 因数列表
        self.min_prime = [0] * (self.ceil + 1)  # 最小因数
        self.primes = []
        self.init_prime_factor()
        return

    def init_min_primes(self):
        # 模板：计算 1 到 self.ceil 所有数字的最小质数因子 min_prime
        # 模板: 收集 1 到 self.ceil 所有质数
        for i in range(2, self.ceil + 1):
            if not self.min_prime[i]:
                self.min_prime[i] = i
                self.primes.append(i)
            for j in range(i * i, self.ceil + 1, i):
                if self.min_prime[j] == 0:
                    self.min_prime[j] = i
            for p in self.primes:
                if i * p > self.ceil:
                    break
                self.min_prime[i * p] = p
                if i % p == 0:
                    break

    def init_prime_factor(self):
        self.init_min_primes()
        # 模板：计算 1 到 self.ceil 所有数字的质数分解（可选）
        for num in range(2, self.ceil + 1):
            i = num
            while num > 1:
                p = self.min_prime[num]
                cnt = 0
                while num % p == 0:
                    num //= p
                    cnt += 1
                self.prime_factor[i].append([p, cnt])
        return
